package numEnclaves

//记录遍历过的坐标
type pairs struct {
	x, y int
}

//四个方向，上下左右
var dir = []pairs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

/*
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

*/
// 广度优先搜素
/*
从方格边界开始找1，找到的1放入队列，然后不断循环队列，从四个方向开始又找1，找到的1加入队列 且把值更新为0
最后遍历方格，没有遍历到的，且为1的则ans++
*/
func numEnclaves(grid [][]int) (ans int) {
	// 长宽
	m, n := len(grid), len(grid[0])

	queue := []pairs{}

	// 矩阵两边找为陆地
	for i := 0; i < m; i++ {
		if grid[i][0] == 1 {
			grid[i][0] = 0
			queue = append(queue, pairs{i, 0})
		}
		if grid[i][n-1] == 1 {
			grid[i][n-1] = 0
			queue = append(queue, pairs{i, n - 1})
		}
	}
	// 矩阵上下找为陆地
	for i := 1; i < n-1; i++ {
		if grid[0][i] == 1 {
			grid[0][i] = 0
			queue = append(queue, pairs{0, i})
		}
		if grid[m-1][i] == 1 {
			grid[m-1][i] = 0
			queue = append(queue, pairs{m - 1, i})
		}
	}

	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]

		for _, pair := range dir {
			// 没越界，是陆地，则加入队列
			if x, y := p.x+pair.x, p.y+pair.y; 0 <= x && x < m && 0 < y && y < n && grid[x][y] == 1 {
				// 这个陆地遍历过了，后续用不上，所以置为0
				grid[x][y] = 0
				queue = append(queue, pairs{x, y})
			}
		}
	}

	// 遍历方格，如果是1，且没有访问过，则是飞地
	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			if grid[i][j] == 1 {
				ans++
			}
		}
	}
	return ans
}
